The present invention relates generally to positioning systems. More particularly, the present invention pertains to the application of a filter, such as the extended Kalman filter, in such positioning systems, or in systems that provide estimates of one or another aspect besides position of the motion of an object, using information acquired from cellular base stations and from satellites.
A satellite positioning system (SATPS) receiver generally determines its positions by triangulating its Line of Sight (LOS) range to several satellites or space vehicles. A GPS receiver, for example, computes a 4-dimensional solution involving latitude, longitude, altitude, and time using the LOS ranges to as few as four satellites. The accuracy of the solution is a direct function of the accuracy of the range measurements.
SATPS receivers are growing rapidly in popularity and application. GPS receivers, for example, are now common in aviation, marine, and terrestrial applications. An increasingly common terrestrial application for GPS receivers is in automobiles. In the automotive context, the vehicle""s location is typically displayed on an electronic display of a street map. It is vital in this context, therefore, to provide the driver with continuously updated position solutions, collectively called a xe2x80x9cground track,xe2x80x9d that accurately track the vehicle""s movement from one moment to the next. Experience shows that consumers consider ground-track fidelity as one of the most important criteria in choosing a receiver. It is extremely important, therefore, that the ground-track displayed on the GPS receiver""s electronic map not have spurious jumps, stair steps, spikes, jigs, or jogs that are unrelated to the vehicle""s actual path.
There are a number of factors, however, that may cause discontinuities in the position solutions used to determine the ground-track of an automotive SATPS receiver. One source of position solution discontinuity is xe2x80x9cSelective Availabilityxe2x80x9d (SA), which restricts the accuracy of civilian GPS receivers to roughly 100 meters. SA is intentionally used by the U.S. Government for purposes of national security. The Department of Defense (DOD) implements SA by purposely injecting error into the satellite range signals.
Another common source of position solution discontinuity is due to the phenomenon known as multi-path, where the true LOS signal from a given satellite reaches the GPS receiver""s antenna, along with additional signals providing supposedly the same information, the additional signals caused by reflection from nearby objects, such as buildings or cliffs. The multi-path phenomenon is particularly troublesome for automotive receivers because they are frequently used in cities and surrounded by tall buildings. This environment is sometimes called an xe2x80x9curban canyonxe2x80x9d due to the canyon-like setting it resembles. Regardless of source, multi-path can be a very vexing problem because the additional signals may be very strong, but very wrong.
Yet another source of position solution discontinuity is that the constellation of satellites used by a SATPS receiver can change; the SATPS receiver may see a different constellation of satellites from one moment to the next. If the GPS receiver is located in an urban canyon environment, for example, individual satellites may become blocked and later unblocked as the receiver moves past different buildings. The discontinuity arises in this situation because the error in a position solution is based on the constellation of satellites used. (Two satellites located in approximately the same direction will provide position information with larger error than two satellites in very different directions, all other things being equal.) If the position solution provided by a GPS receiver is suddenly based on a different constellation, the different error may cause a jump or discontinuity in position.
It is known in the art to use a Kalman filter to account for the uncertainties in measurement data provided to a positioning system receiver. FIG. 1 is a simplified flow diagram of a conventional GPS-type positioning system 10 including an RF antenna 11, a measurement engine 12 and a Kalman filter 14, providing a position estimate {circumflex over (x)}(k) for position at time instant k. The measurement engine 12 receives RF signals from a plurality of orbiting satellites via the antenna 11 and provides the Kalman filter 14 with measured position and velocity, i.e. measured state information as opposed to the predicted state information provided by the Kalman filter based on the measured values.
The construction of the measurement engine 12 varies from application to application. Generally, the measurement engine 12 contains the analog electronics (e.g. preamplifiers, amplifiers, frequency converters, etc.) needed to pull in the RF signal, and further includes a code correlator for detecting a particular GPS code corresponding to a particular satellite. The measurement engine 12 estimates the line of sight (LOS) range to a detected satellite using a local, onboard GPS clock and data from the satellite indicating when the satellite code was transmitted. The LOS ranges determined this way are called pseudo-ranges because they are only estimates of the actual ranges, based on the local detection time. In the positioning system 10 of FIG. 1, the measurement engine 12 converts the pseudo-ranges it acquires over time to measurements z(k) of the state of the process, i.e. to a position and velocity of the moving object whose position is being determined.
In estimating the state x(k) of a process (such as the motion of a vehicle), a (standard) Kalman filter relies on the assumption that the process evolves over time according to a linear stochastic difference equation, such as:
x(k+1)=A(k)xc3x97(k)+Bu(k)+w(k)xe2x80x83xe2x80x83(1)
where w(k) is the process noise, A(k) is an nxc3x97n matrix relating the state at time step k to the state at time step k+1 in the absence of a driving function, u(k) is a control input to the state x, and B is an nxc3x97l matrix that relates the control input to the state x. A standard Kalman filter further relies on the assumption that the measurements used by the Kalman filter in estimating the state of the process are linearly related to the state of the process, i.e. that a measurement z(k) (i.e. the measured position at time instant k) is corresponds to the state x(k) (i.e. the actual position at time instant k) according to an equation of the form:
z(k)=H(k)xc3x97(k)+s(k)xe2x80x83xe2x80x83(2)
where s(k) is the measurement noise, and the mxc3x97n matrix H relates the state x(k) to the measurement z(k). If either of these assumptions do not apply, a standard Kalman filter cannot be used, or at least not used without first deriving from information provided (by e.g. satellites) about the process measurement data that is, at least approximately, linearly related to the state of the process, and at least not without taking measurements at close enough intervals that the effects of any non-linearity in the evolution of the process does not become important from one measurement to the next.
In the case of a positioning system in a vehicle where the positioning system uses information from satellites as the basis for position measurements, the dependence between the state (position, but in general also velocity) of the process (motion of the vehicle hosting the positioning system), and the position measurements is non-linear, i.e. instead of equation (2), the satellite provides a pseudo-range:       ρ    ⁡          (      k      )        =                              ∑                      i            =            1                    3                ⁢                              [                                                            x                  i                                ⁡                                  (                  k                  )                                            -                                                x                  i                  s                                ⁡                                  (                  k                  )                                                      ]                    2                      +          ct      o      
in which xi(k) is, e.g. the ith component of the three-dimensional position of the vehicle, xis is the same for the satellite, to is a clock offset between the positioning system clock in the vehicle and the satellite clock, and c is used to designate the speed of light.
It is known in the art, generally, that in case either of the assumptions on which a standard Kalman filter relies is violated, a so-called extended Kalman filter can be used. (Sometimes what is called a converted-measurement Kalman filter (CMKF) is used, instead of an extended Kalman filter, in case of non-linear measurements.) In such a filter, there is a linearizing about the current mean and covariance of the estimated state of a process and for the measurements used in estimating the state of the process. This linearizing makes possible the use of a Kalman-type filter in estimating the state of a process, an approach that is recursive (the solution at a preceding instant, along with a current measurement, leading to the solution at the next instant), as compared with other approaches, such as iterative or direct solution, that rely on the current measurement (alone) for solution.
Although extended Kalman filters are known in the art, the prior art does not teach using such a filter, or using other types of filters, in a positioning system based on information provided by cellular base stations, or, ideally by both cellular base stations and satellites, so that at any one instant of time, information either from only cellular base stations, or from both cellular base stations and satellites, are used as one measurement of the state of the system.
What is further needed is a way for a positioning system to combine multiple such measurements, at any instant of time, so as to further increase the reliability of the positioning system. Since cellular base station data does not suffer from the same errors as affect satellite data, a positioning system can be made more reliable if it uses both kinds of data separately and simultaneously, providing therefore at least two measurements at the same instant of time, one purely based on satellite data and one purely based on cellular data. (The main sources of noise and inaccuracy in cellular data are not the same as for satellites; instead of atmosphere, multi-path, and selective availability, error in a cellular system is caused by obstacles in the signal path, range measurement quantization, and interfering frequencies.)
Even though the use of two different types of sources of positioning measurements can provide an inherently more reliable positioning system, it is still true that at any instant of time a particular measurement or a particular as piece of information on which a measurement is based can be greatly impaired by one or another source of error (not usually the selective diversity, which is intended only to xe2x80x9cditherxe2x80x9d the correct measurement). Thus, it remains advantageous, even in case of a hybrid positioning system (hybrid in the sense of different kinds of sources of measurement), to systematically eliminate some measurements or some pieces of information (e.g. a pseudo-range value) from which a measurement is determined (by triangulation of several pseudo-range values), the eliminating based on statistical measures of the error of the measurements or pieces of information.
Accordingly, the present invention provides a filter for a generalized positioning system, and also a corresponding generalized positioning system and method. All of these are based on using information from cellular base stations, at least part of the time, in providing a succession of estimates of one or another aspect of the state of motion of an object, such as estimates of position or velocity or both. The generalized positioning system includes: a filter, responsive to an initial estimate of a state of motion of the object, and an initial value of state covariance, and further responsive to a succession of measurements of the state, each corresponding to a different instant of time, for statistically determining the succession of state estimates; and a measurement engine, responsive to information provided by cellular base stations, from which a measurement of the state can be determined, for providing the succession of measurements of the state. In some aspects of the invention, the filter is a non-linear filter, such as an extended Kalman filter, and in other aspects of the invention the filter is a linear filter.
In a further aspect of the invention, the generalized positioning system also includes: means for determining association probabilities for a plurality of state measurements all at a same instant of time, each association probability corresponding to a particular state measurement at the instant of time, and also means for determining an association probability providing a value for the probability that none of the plurality of measurements is correct; means for combining into a single measurement innovation each individual innovation using the association probabilities as weightings; and means for determining the covariance of the updated state based on the individual association probabilities, the association probability for providing a value for the probability that none of the measurements is correct, and the combined measurement innovation.
In another aspect of the invention, the filter of the generalized positioning system is responsive to measurements provided by a measurement engine receiving information from both satellites and cellular base stations.
In yet another aspect of the invention, the generalized positioning system also includes an output display, wherein both the measurement engine and the output display are co-located with the object for which the state information is to be measured, and further wherein the filter, the means for determining association probabilities, the means for combining into a single measurement innovation each individual innovation, and the means for determining the covariance of the updated state are all hosted by a non-local facility, one that is separate and remote from the object for which the state information is to be measured, and wherein the non-local facility and the measurement engine and the output display are in radio communication.
In yet still another aspect of the invention, the generalized positioning system filter is responsive to a finite gate width xcex3 of a validation region, and rejects a measurement if it falls outside the validation region.
In yet even a further aspect of the invention, the generalized positioning system also includes: an output display, wherein both the measurement engine and the output display are co-located with the object for which the state information is to be measured, and further wherein the filter is hosted by a non-local facility, one that is separate and remote from the object for which the state information is to be measured, and wherein the non-local facility and the measurement engine and the output display are in radio communication.
In one particular application, the generalized positioning system filter is an extended Kalman filter (EKF).